package leetcode.sword;

import java.util.ArrayList;
import java.util.List;

class Solution90 {

    public static void main(String[] args) {
//        Solution90 s = new Solution90();
//        int[] nums = {1,2,2};
//        System.out.println(s.subsetsWithDup(nums));
        StringBuilder sb = new StringBuilder("12233");
        sb.append('c');
        System.out.println(sb.toString());
        char[] c = sb.toString().toCharArray();
        System.out.println(sb.toString());

    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //剪枝法

        //保存子集的返回值和暂存值
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> cur = new ArrayList<>();

        //用于区分当前访问元素是同一递归层还是不同递归层
        boolean[] visited = new boolean[nums.length];

        //开始回溯
        backTracking(res, cur, visited, nums, 0);
        return (List)res;
    }

    public void backTracking(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> cur, boolean[] visited, int[] nums, int idx){
        res.add(new ArrayList<>(cur));
        for(int i=idx;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]&&!visited[i-1]){
                continue;
            }
            cur.add(nums[i]);
            visited[i] = true;
            backTracking(res, cur, visited, nums, i+1);
            cur.remove(cur.size()-1);
            visited[i] = false;
        }
    }
}